package com.cdream.basic.algorithm.leetcode.bag;

import cn.hutool.json.JSONUtil;

/**
 * @author cdream
 * @date 6/7/21
 */
public class OriginalBag {
    public static void main(String[] args) {
        new OriginalBag().bag2();
    }

    public void bag() {
        int[] weights = new int[]{1, 3, 4};
        int[] values = new int[]{15, 20, 30};
        int beginWeight = 4;
        // 二维数组：状态定义:dp[i][j]表示从0-i个物品中选择不超过j重量的物品的最大价值
        int[][] dp = new int[4][5];
        //表示只选取0号物品最大价值
        // for (int i = weights[0]; i < beginWeight + 1; i++) {
        //     dp[0][i] = values[0];
        // }

        int n = weights.length;
        // w表示选择第几号产品
        for (int w = 1; w <= n; w++) {
            int weight = weights[w - 1];
            // i代表最大的重量，weight代表新产品的重量
            for (int i = 0; i <= beginWeight; i++) {
                if (i < weight) {
                    // 如果新产品大于最大重量，那么直接用上一个产品的重量计算
                    dp[w][i] = dp[w - 1][i];
                } else {
                    // 如果小于最大重量，那么比较用上一个产品计算和选择这个新产品的价值
                    dp[w][i] = Math.max(dp[w - 1][i], dp[w - 1][i - weight] + values[w - 1]);
                }
            }
        }
        System.out.println(JSONUtil.toJsonPrettyStr(dp));
        System.out.println(dp[3][4]);

    }

    public void bag2() {
        int[] weights = new int[]{1, 3, 4};
        int[] values = new int[]{15, 20, 30};
        int beginWeight = 4;
        // 起始重量为beginWeight 的最值
        int[] dp = new int[5];


        int n = weights.length;
        // w表示选择第几号产品
        for (int w = 1; w <= n; w++) {
            int weight = weights[w - 1];
            // i代表最大的重量，weight代表新产品的重量
            for (int totalWeight = beginWeight; totalWeight >= weight; totalWeight--) {
                dp[totalWeight] = Math.max(dp[totalWeight], dp[totalWeight - weight] + values[w - 1]);
            }
        }
        System.out.println(JSONUtil.toJsonPrettyStr(dp));
        System.out.println(dp[4]);

    }
}
